﻿using System;


/*模块的使用demo如下*/
//class Student
//{
//    public int m_age;
//    public string m_name;

//    public Student(int age, string name)
//    {
//        m_age = age;
//        m_name = name;
//    }


//}

//Student[] stu = new Student[] {
//                new Student(1,"c"),
//                new Student(10, "a"), new Student(11, "a") ,new Student(8, "a"),
//                new Student(6, "b"), new Student(11, "b") ,new Student(8, "b")
//            };

//int[] indexs = new int[stu.Length];
//            for (int i = 0; i<indexs.Length; i++)
//            {
//                indexs[i] = i;
//            }


//            int[] indexs2 = CustomSort.MergeSort(indexs, delegate (int index1, int index2)
//            {
//                int r = stu[index1].m_age.CompareTo(stu[index2].m_age);

//                if (r <= 0)
//                {
//                    return true;
//                }
//                else
//                {
//                    return false;
//                }
//            });
//            for (int i = 0; i<indexs.Length; i++)
//            {
//                Console.WriteLine(string.Format("({0}, {1})", stu[indexs2[i]].m_age, stu[indexs2[i]].m_name));
//            }
//            Console.WriteLine("-----------------------------------------------------------------------");

//            int[] indexs3 = CustomSort.MergeSort(indexs2, delegate (int index1, int index2)
//            {
//                int r = stu[index1].m_name.CompareTo(stu[index2].m_name);

//                if (r <= 0)
//                {
//                    return true;
//                }
//                else
//                {
//                    return false;
//                }
//            });
//            for (int i = 0; i<indexs.Length; i++)
//            {
//                Console.WriteLine(string.Format("({0}, {1})", stu[indexs3[i]].m_age, stu[indexs3[i]].m_name));
//            }
//(1, c)
//(6, b)
//(8, a)
//(8, b)
//(10, a)
//(11, a)
//(11, b)
//-----------------------------------------------------------------------
//(8, a)
//(10, a)
//(11, a)
//(6, b)
//(8, b)
//(11, b)
//(1, c)
namespace NOCSort
{
    class CustomSort
    {
        public delegate bool LessEqual(int a, int b);
        public static LessEqual m_lessEqual;
        public static int[] MergeSort(int[] arr, LessEqual lessEqualDelegate)
        {
            m_lessEqual = lessEqualDelegate;

            int length = arr.Length;
            if (length < 2)
            {
                return arr;
            }
            int middle = length / 2;
            int[] left = new int[middle], right = new int[length - middle];
            Array.Copy(arr, left, middle); // 左序列为[0,...,mindle-1]，长度为mindle
            Array.Copy(arr, middle, right, 0, length - middle); // 右序列为[mindle,...,length-1]，长度为length-middle

            return Merge(MergeSort(left, lessEqualDelegate), MergeSort(right, lessEqualDelegate));
        }

        // 对两个已排序的子序列进行合并
        private static int[] Merge(int[] left, int[] right)
        {
            int[] result = new int[left.Length + right.Length];
            int flagLeft = 0, flagRight = 0, flag = 0;

            // 算法同二项式相加的算法类似
            while (flagLeft < left.Length && flagRight < right.Length)
            {
                //if (left[flagLeft] <= right[flagRight])
                if (m_lessEqual(left[flagLeft], right[flagRight]))
                {
                    result[flag++] = left[flagLeft++];
                }
                else
                {
                    result[flag++] = right[flagRight++];
                }
            }

            while (flagLeft < left.Length)
            {
                result[flag++] = left[flagLeft++];
            }

            while (flagRight < right.Length)
            {
                result[flag++] = right[flagRight++];
            }

            return result;
        }
    }
}
